#include <stdio.h>
#include <math.h>
long int a[9999999],b[9999999];

int main()
{
    long long int T,n,i,j,k,l,m,x,y,z=0;

    scanf("%lld",&T);

    for(i=1;i<=T;i++)
    {
        scanf("%lld",&j);//输入数据
        for(k=0;k<j;k++)//比j小的正整数
        {
            l=j^k;
            m=sqrt(l);

            for(n=2;n<=m;n++)
                if(l%n==0)
                    break;

            if(n>=m+1 && l!=1)
                z++;
        }

        b[i]=z;
        z=0;
    }

    for(i=1;i<=T;i++)
        printf("%lld\n",b[i]);

    return 0;
}